
//2684.矩阵中移动的最大次数
class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int n=grid.size(),m=grid[0].size();
        int dx[]={0,-1,1};
        
        vector<vector<int>> vist(n,vector<int>(m,-1));  //记录每一个位置的结果

        function<int(int,int)> dfs=[&](int x,int y)
        {
            if(vist[x][y]!=-1) return vist[x][y];  //如果前面已经记录过就直接返回
            int ret=0;
            for(int k=0;k<3;k++)
            {
                int a=x+dx[k],b=y+1;
                if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]>grid[x][y]) 
                    ret=max(ret,dfs(a,b)+1);
            }
            vist[x][y]=ret;  //将记录的结果存储起来
            return ret;
        };        

        int ans=0;
        for(int i=0;i<n;i++)
            ans=max(ans,dfs(i,0));
        return ans;
    }
};